from collections import *
from itertools import *
from functools import *
from bisect import *
from heapq import *
import math
import sys
import struct
IN = lambda: sys.stdin.readline().rstrip("\r\n")
PN = lambda x: sys.stdout.write(x)
I = lambda: int(IN())
S = lambda: IN().split()
M = lambda: map(int, IN().split())
L = lambda: list(map(int, IN().split()))
G = lambda: map(lambda x: int(x) - 1, IN().split())
def array(shape, value = 0):
if len(shape) == 0:
return value
else:
return [array(shape[1:], value = value) for _ in range(shape[0])]
mod = 1000000007
def qpow(a, b, p = mod):
res = 1
while b:
if b & 1:
res = res * a % p
a = a * a % p
b >>= 1
return res
mod = 998244353
class Comb:
def __init__(self, n, p = mod):
self.__fac = [0 for _ in range(n + 1)]
self.__ifac = [0 for _ in range(n + 1)]
self.__fac[0] = 1
self.__mod = p
for i in range(1, n + 1):
self.__fac[i] = i * self.__fac[i - 1] % self.__mod
self.__ifac[n] = qpow(self.__fac[n], mod - 2)
for i in range(n - 1, -1, -1):
self.__ifac[i] = (i + 1) * self.__ifac[i + 1] % self.__mod
def binom(self, a, b):
if a < b or b < 0:
return 0
return self.__fac[a] * self.__ifac[b] * self.__ifac[a - b] % self.__mod
def fac(self, n):
return self.__fac[n]
def ifac(self, n):
return self.__ifac[n]
a, b, m = M()
n = a + b
e = [0 for _ in range(m + 1)]
deg = [0 for _ in range(n + 1)]
for i in range(1, m + 1):
u, v = M()
v += a
e[i] = (u, v)
deg[u] += 1
deg[v] += 1
ans = max(deg)
match = [[0 for _ in range(n + 1)] for __ in range(n + 1)]
for i in range(1, m + 1):
c1, c2 = 1, 1
u, v = e[i]
while match[u][c1]:
c1 += 1
while match[v][c2]:
c2 += 1
match[u][c1] = v
match[v][c2] = u
if c1 == c2:
continue
c0, w = c2, v
while w != 0:
match[w][c1], match[w][c2] = match[w][c2], match[w][c1]
w = match[w][c0]
c0 ^= c1 ^ c2
def getans(i):
u, v = e[i]
for j in range(1, ans + 1):
if match[v][j] == u:
return j
return -1
print(ans)
for i in range(1, m + 1):
print(getans(i), end = ' ')
// hiensumi: Maybe, success will come tomorrow. Thus, just keep trying! =) "Z/x
#include "bits/stdc++.h"
#define fod(i,a,b) for(int i = a;i <= b; i++)
#define fok(i,a,b) for(int i = a;i >= b; i--)
#define ll long long
#define int long long
#define fi first
#define se second
#define mask(i) (1LL<<(i))
#define BITpos(a,i) ((a >> i) & 1LL)
#define pb push_back
#define el '\n'
#define all(v) v.begin(), v.end()
#define odd(i) (i & 1LL)
using namespace std;
typedef pair<int, int> ii;
const int MOD = 1e9 + 7;
inline void kill(){cerr << "\nTime: " << clock() << "ms\n"; cerr << "⏁⊑⟒ ⋔⍜⍜⋏ ⍙⏃⌇ ⌇⍜ ⏚⟒⏃⎍⏁⟟⎎⎍⌰ ⏁⊑⏃⏁ ⏁⊑⟒⍀⟒ ⍙⏃⌇ ⏃ ⋔⟟⍀⍀⍜⍀ ⟟⋏ ⏁⊑⟒ ⍜☊⟒⏃⋏.\n"; exit(0);}
inline void add(int &x, int y, int mod = MOD) { x += y; while (x >= mod) x -= mod; while (x < 0) x += mod;}
inline void mul(int &x, int y, int mod = MOD) { x = (x * 1LL * y) % mod;}
inline int bpow(int x, int y, int mod = MOD) { int ans = 1; while (y) { if (y & 1) mul(ans, x, mod); mul(x, x, mod); y >>= 1;} return ans;}
inline int bp(int a, int b){int res = 1; while (b > 0) {if (b & 1) res = res * a; a = a * a; b >>= 1; } return res;}
inline int Inv(int x, int mod = MOD) { return bpow(x, mod - 2, mod);}
inline int Div(int x, int y, int mod = MOD) { int tmp = x; mul(tmp, Inv(y, mod), mod); return tmp;}
template<class T> bool mini(T& a,T b){return (a>=b)?a=b,1:0;}
template<class T> bool maxi(T& a,T b){return (a<=b)?a=b,1:0;}
struct point{int x, y;};
struct edge{int u, v, c;};
//int find(int u){if (lab[u] < 0) return u; return lab[u] = find(lab[u]);}
//bool join(int u, int v){u = find(u);v = find(v);if(u == v) return 0;if(lab[u] > lab[v]) swap(u,v);lab[u] += lab[v];lab[v] = u; return 1;}
const ll INF = 1e18, base = 1e6 + 5, multitest = 0;
//"Life is a daring adventure or it is nothing at all." -Helen Keller...
//"Success isn't determined by how many times you win, but by how you play the week after you lose." -Pele...
#define name ""
#define ld long double
// remember to reset value for multitestcase
// she is your motivation!!!
void init(){
}
int a, b, m, match[base];
vector <int> g[base];
vector <ii> hn;
void inp(){
cin >> a >> b >> m;
fod(i,1,m){
int u, v; cin >> u >> v;
g[u].pb(v + a);
g[v+a].pb(u);
hn.pb(ii(u,v));
}
}
namespace sub_task1{
int ans[1005][1005], dd[base];
bool konig(int u, int cnt, int color){
if(dd[u] == cnt) return 0;
dd[u] = cnt;
for(int v : g[u]){
bool ch = u > a and g[match[v]].size() < color;
if(ch or match[v] == 0 or konig(match[v], cnt, color)){
if(ch) match[match[v]] = 0;
match[v] = u;
match[u] = v;
return 1;
}
}
return 0;
}
void solve(){
int res = 0;
fod(i,1,a+b) maxi(res, (int)g[i].size());
cout << res << el;
int cnt = 0;
fok(color, res, 1){
fod(i,1,a+b) match[i] = 0;
fod(i,1,a+b){
if(match[i] == 0 and g[i].size() == color){
konig(i,++cnt,color);
}
}
fod(u,1,a) if(match[u] != 0){
int v = match[u];
ans[u][v-a] = color;
g[u].erase(find(all(g[u]), v));
g[v].erase(find(all(g[v]), u));
}
}
for(auto [u,v] : hn){
cout << ans[u][v] << " ";
}
}
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if(fopen(name".inp", "r")){
freopen(name".inp", "r", stdin);
freopen(name".out", "w", stdout);
}
int Test = 1; if(multitest) cin >> Test;
init();
while(Test--){
inp();
sub_task1 :: solve();
}
kill();
}
/*
Trú mưa nơi gốc cây ngày xưa
Để nhìn em lần cuối trong mưa
Để nắm tay đưa em đi về
Chốn mộng mơ...
Có hôm mây gió chợt ca vang
Nụ cười em như nắng mùa thu sang
Làm lòng tôi xao xuyến mà lang thang
Nghĩ về em...
Mình tôi thao thức
mình tôi day dứt
Cớ sao em không về với tôi
Mình tôi thao thức
mình tôi day dứt
Cớ sao em không cười với tôi
Gió mang câu ca về nơi đây
gió mang câu ca về với đời em
Nắng mang câu thơ về nơi đây
chính em mang thơ về với tình ta ...
Chiếc radio của em
Và từng ly trà đá ly kem
Cùng hát lên câu ca êm đềm
giữa mùa yêu
Những bông hoa xanh ngoài hiên
Vào buổi chiều tràn nắng an nhiên
Ta ngồi bên cạnh nhau
ngắm mùa thu sang...
*/
383. Ransom Note | 242. Valid Anagram |
141. Linked List Cycle | 21. Merge Two Sorted Lists |
203. Remove Linked List Elements | 733. Flood Fill |
206. Reverse Linked List | 83. Remove Duplicates from Sorted List |
116. Populating Next Right Pointers in Each Node | 145. Binary Tree Postorder Traversal |
94. Binary Tree Inorder Traversal | 101. Symmetric Tree |
77. Combinations | 46. Permutations |
226. Invert Binary Tree | 112. Path Sum |
1556A - A Variety of Operations | 136. Single Number |
169. Majority Element | 119. Pascal's Triangle II |
409. Longest Palindrome | 1574A - Regular Bracket Sequences |
1574B - Combinatorics Homework | 1567A - Domino Disaster |
1593A - Elections | 1607A - Linear Keyboard |
EQUALCOIN Equal Coins | XOREQN Xor Equation |
MAKEPAL Weird Palindrome Making | HILLSEQ Hill Sequence |